package 回溯算法.括号生成;

import java.util.LinkedList;
import java.util.List;

public class 括号生成_22 {
    public static void main(String[] args) {
        System.out.println(new 括号生成_22().generateParenthesis(3));
    }

    List<String> res = new LinkedList<>();

    public List<String> generateParenthesis(int n) {
        if (n == 0) {
            return res;
        }

        backtrack(n, n, "");
        return res;
    }

    /*left、right可用的左、右括号数量 str为路径*/
    public void backtrack(int left, int right, String str) {
        //一些结束条件
        if (left < 0 || right < 0) {
            return;
        }
        //剩下的左括号多余右括号，不合法。证明生成的括号中左括号少于右括号
        if (left > right) {
            return;
        }
        //左右括刚好用完，组成了合法的括号。不合法的情况在上两个if已经剔除了
        if (left == 0 && right == 0) {
            res.add(str);
        }


        /*本来回溯模板要遍历选择列表，但是本题的选择列表是两个独立的情况，所以单独写出来就好*/

        //加入到路径
        str = str + "(";
        //进入下一层决策
        backtrack(left - 1, right, str);
        //撤销选择
        str = str.substring(0, str.length() - 1);

        //加入到路径
        str = str + ")";
        //进入下一层决策
        backtrack(left, right - 1, str);
        //撤销选择
        str = str.substring(0, str.length() - 1);
    }
}
